In general, digital communication networks are utilized in which messages or streams of information are subdivided into sequences of small units called packets or cells, in which such cells or packets are transmitted from node to node, and in which at each node a switch selects both the order of transmitting such cells or packets and the next node to which they are to be transmitted, so that in such networks the digital information reaches its ultimate destination in a timely manner. It is desirable that these network switches be capable of supporting network traffic of various characteristics including traffic requiring hard real-time guarantees of timely delivery, continuous media traffic for audio and video, and traffic requiring very rapid response.
One important kind of digital communications network is called an ATM or Asynchronous Transfer Mode network. ATM networks provide for the transmission of data from one point or node in the network to one or more other points or nodes by the subdivision of the data or information into sequences of small cells of fixed size which are then transmitted through the network from node to node. Such nodes include ATM switches which provide fast packet or cell switching and routing between nodes of the network. General principles of ATM networks are described in articles by J. Bryan Lyles and Daniel C. Swinehart, "The Emerging Gigabit Environment and the Role of Local ATM," IEEE Communications Magazine, vol. 30, #4, April 1992, pp. 52-58, and by C. Lamb, "Speeding to the ATM," Unix Review, vol. 10, #10, October 1992, pp. 29-36.
One of the major problems with ATM networks is the problem of scheduling of cells to be transmitted by each switch. The cells are in general buffered at each switch in queues. Assuming no congestion, these cells are received from an incoming link at a switch and immediately transmitted over an outgoing link to another destination. However, when cells arrive over multiple input links and must be transmitted onto the same output link at the same time, it is necessary to form a queue of cells so that they can be transmitted in the desired order.
In order to accommodate the scheduling of which cells are to be transmitted at what time and in what order, it is common to utilize a First In-First Out, FIFO, ordering system in which the first cell to arrive at the switch is transmitted prior to subsequently arriving cells. In the case of networks which support real time applications, cells are also typically assigned priorities and stored in separate queues by priority. Subsequently, cells are transmitted in the order dictated by the priorities of the separate queues. It will be appreciated that these simple systems can only support a limited number and class of real time applications, because the FIFO and priority scheduling mechanisms can only provide limited guarantees of timely transmission without loss of data.
For instance, first generation switches for ATM local and wide area networks provide very simple scheduling algorithms for scheduling and dispatching communication traffic from incoming to outgoing network links. Traffic is handled in FIFO order according to the ATM rules, but a small number of priority levels, usually two, are provided to support applications with real-time communication requirements in a very limited way. Unfortunately, a handful of statically assigned priorities is barely adequate for even moderate-sized local area networks with a lot of advanced, rapidly evolving applications. Furthermore, when applications need to transmit continuous media, such as audio and video, or when they need predictable response in real time, it is virtually impossible to make any kind of predictions or guarantees about the quality and timeliness of network service.
Over the past two decades, there has been considerable research in real time and multi-media computing and communication, and many scheduling algorithms have been invented and studied in great detail. For instance, J. Jungok Bae and T. Suda, in an article entitled "Survey of Traffic Control Schemes and Protocols in ATM Networks," Proceedings of the IEEE, vol. 79, No. 2, February 1991, pp. 170-189, describe a large number of traffic control schemes which must be accommodated by any general purpose scheduling mechanism in an ATM switch. Moreover, H. Zhang, et. al., describe rate-based service disciplines and rate controlled static-priority queuing in the following papers: H. Zhang and S. Keshav, "Comparison of RateBased Service Disciplines," Proceedings of ACM SIGCOMM '91, Zurich, September, 1991, and H. Zhang and D. Ferrari, "Rate-Controlled Static-Priority Queueing," International Computer Science Institute Tech. Report #TR-92-003, Berkeley, Calif. Further examples of scheduling algorithms can be found in the following papers and articles: W. A. Horn, "Some Simple Scheduling Algorithms," Naval Research Logistic Quarterly, Vol. 21, 1974, pp. 177-185; J. R. Jackson, "Scheduling a Production Line to Minimize Maximum Tardiness," Management Science Research Project, Research Report 43, UCLA, January 1955; C. R. Kalmanek, H. Kanakia, S. Keshav, "Rate controlled servers for very high-speed networks, "IEEE Global Telecommunications Conference, San Diego, Calif., December 1990, pp. 300.3.1-300.3.9; A. Kumar, J. Parekh, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks," PhD dissertation, MIT, February 1992; H. T. Kung, A. Chapman, "The FCVC (Flow-Controlled Virtual Channels) Proposal for ATM Networks," Proceeding of 1993 International Conference on Network Protocols, San Francisco, Calif., Oct. 19-22, 1993; C. L. Liu and J. W. Layland, "Scheduling Algorithms for multiprogramming in a Hard-Real-Time Environment," Journal of ACM, vol. 20, No. 1, 1973; L. Zhang, "Virtual Clock: A new traffic control algorithm for packet switching networks," in Proceedings ACM SIG-COMM, Philadelphia, Pa., September 1990. pp. 19-29; L. Zhang, "Virtual Clock: A new traffic control algorithm for packet-switched networks," ACM Transactions on Computer Systems, vol. 9, No. 2, May 1991, pp 101-124; Q. Zheng, K. Shin, "On the Ability of Establishing Real-time Channels in Point-to-Point Packet-switched Networks," IEEE Transactions on Communications, March 1994.
Note that most of these algorithms have been considered inappropriate for implementation in ATM networks, partly because they require slow searches of queues and partly because they are too specialized for general purpose environments.
However, one type of VLSI Sequencer Chip for ATM scheduling is described in a paper by H. Jonathan Chao and Necdet Uzun, "A VLSI Sequencer Chip for ATM Traffic Shaper and Queue Manager," IEEE Journal of Solid-State Circuit, Vol. 27, No. 11, November 1992. In this system, cells are switched to output ports, each of which contains its own queue and sequencer chip, where such cells are sorted by the sequencer chip into priority order. While this provides for an improved implementation of priority scheduling, it requires separate sorting circuitry for each output port of the switch, resulting in increased cost, decreased flexibility in switch design and potential limitations of performance.
One significant enhancement of ATM switches involving shared-buffer scheduling is described in two papers by H. Kondoh, et al, and K. Oshima, et al: H. Kondoh, H, Yamanaka, M. Ishiwaki, Y. Matsuda, and M. Nakaya, "An Efficient Self-Timed Queue Architecture for ATM Switch LSI's," Custom Integrated Circuit Conference, San Diego, May 1994; and K. Oshima, H. Yamanaka, H. Saito, H. Yamada, S. Kohama, H. Kondoh, Y. Matsuda, "A New ATM Switch Architecture based on STS-type Shared Buffering and its LSI Implementation," Proceedings of International Switching Symposium '92, Yokohama, Japan, October 1992, pp. 359-363. The key element of this ATM switch design is common queuing, shared buffers to improve statistical multiplexing, and both faster performance and lower cost. This switch is distinguished from other ATM switches which use output buffering, in that input cells from all input ports are deposited directly into a common buffer memory. Output is selected on a FIFO or simple priority basis. While this switch operates satisfactorily for long distance telecommunications with simple priority requirements, there is no control of the queuing to support real time applications such as factory automation, power plant control, and full-motion video.